e04naf

e04naf © Numerical Algorithms Group, 2002.

Purpose

E04NAF Quadratic programming problem (comprehensive)

Synopsis

[x,iter,obj,clamda,istate,ifail] = e04naf(bl,bu,qphess,x<,cvec,a,hess,lp,...
cold,istate,featol,msglvl,itmax,bigbnd,orthog,ifail>)

Description


 E04NAF is designed to solve the quadratic programming (QP) 
 problem - the minimization of a quadratic function subject to a 
 set of linear constraints on the variables. The problem is 
 assumed to be stated in the following form:
 
                  T   1 T                    (x )            
       Minimize  c x+ -x Hx   subject to  l<=(Ax)<=u ,         (1)
                      2                                      
 
 where c is a constant n-vector and H is a constant n by n 
 symmetric matrix; note that H is the Hessian matrix (matrix of 
 second partial derivatives) of the quadratic objective function. 
 The matrix A is m by n, where m may be zero; A is treated as a 
 dense matrix.
 
 The constraints involving A will be called the general 
 constraints. Note that upper and lower bounds are specified for 
 all the variables and for all the general constraints. The form 
 of (1) allows full generality in specifying other types of 
 constraints. In particular, an equality constraint is specified 
 by setting l =u . If certain bounds are not present, the 
             i  i                                        
 associated elements of l or u can be set to special values that 
 will be treated as -infty or +infty.
 
 The user must supply an initial estimate of the solution to (1), 
 and a subroutine that computes the product Hx for any given 
 vector x. If H is positive-definite or positive semi-definite, 
 E04NAF will obtain a global minimum; otherwise, the solution 
 obtained will be a local minimum (which may or may not be a 
 global minimum). If H is defined as the zero matrix, E04NAF will 
 solve the resulting linear programming (LP) problem; however, 
 this can be accomplished more efficiently by setting a logical 
 variable in the call of the routine (see the parameter LP).
 
 E04NAF allows the user to provide the indices of the constraints 
 that are believed to be exactly satisfied at the solution. This 
 facility, known as a warm start, can lead to significant savings 
 in computational effort when solving a sequence of related 
 problems.
 
 The method has two distinct phases. In the first (the LP phase), 
 an iterative procedure is carried out to determine a feasible 
 point. In this context, feasibility is defined by a user-provided
 array FEATOL; the jth constraint is considered satisfied if its 
 violation does not exceed FEATOL(j). The second phase (the QP 
 phase) generates a sequence of feasible iterates in order to 
 minimize the quadratic objective function. In both phases, a 
 subset of the constraints - called the working set - is used to 
 define the search direction at each iteration; typically, the 
 working set includes constraints that are satisfied to within the
 corresponding tolerances in the FEATOL array.
 

Parameters

e04naf

Required Input Arguments:

bl (:)                                real
bu (:)                                real
qphess                                function (User-Supplied)
x (:)                                 real

Optional Input Arguments:                       <Default>

cvec (:)                              real     zeros(length(x),1)
a (:,:)                               real     zeros(1,length(x))
hess (:,:)                            real     0
lp                                    logical  0
cold                                  logical  1
istate (:)                            integer  zeros(length(bu),1)
featol (:)                            real     sqrt(eps)*ones(length(bu),1)
msglvl                                integer  1
itmax                                 integer  50
bigbnd                                real     1e10
orthog                                logical  1
ifail                                 integer  -1

Output Arguments:

x (:)                                 real
iter                                  integer
obj                                   real
clamda (:)                            real
istate (:)                            integer
ifail                                 integer